Programación Avanzada

1 Contenido de la clase

Repaso: de la resolución a la demostración automática [00:00-02:35]

Se repasa la regla de resolución: si se tiene P ∨ Q y ¬Q, se concluye P (equivalente al modus ponens: si Q implica P y Q, entonces P) [00:34-00:59]. La idea es automatizar los métodos de prueba: Robinson propuso un método automático de demostración siguiendo esta regla [00:26-00:38]. En la práctica, cuando se demuestra algo se manejan negaciones y conclusiones, y los términos positivos/negativos que coinciden se eliminan [01:04-01:27].

El inconveniente: explosión combinatoria [01:31-02:10, 06:58-07:24]

El método de prueba por resolución tiene un inconveniente: la explosión combinatoria es muy grande cuando hay varias fórmulas, porque hay que probar muchas combinaciones de literales (este se va con este, este se llega con este…) [01:31-01:58, 06:58-07:24]. La solución es restringir la demostración a un subconjunto del cálculo de predicados para reducir esa explosión [02:00-02:08].

Ejemplo de resolución con predicados [02:35-04:53]

Se muestra cómo aplicar la resolución a un conjunto de cláusulas con predicados, por ejemplo R(x) ∨ F(x), ¬F(x) ∨ T(x) (donde R, F y T son predicados como "estudia", "trabaja", "va al cine") [02:47-03:29]. La idea es demostrar una conclusión: se niega la meta, se agrega al conjunto y se aplica la resolución hasta llegar a la cláusula vacía (contradicción); si se llega a la vacía, la meta se sigue de las premisas [03:27-04:44]. En la práctica se niega la meta y se van cancelando los literales opuestos (no F con F, no R con R, etc.) hasta llegar a la contradicción [04:16-04:44].

Prolog: el lenguaje de la programación lógica [06:44-09:32]

Después de la resolución se presenta Prolog. Se mencionan varias versiones e implementaciones del lenguaje: SWI-Prolog, Visual Prolog y GNU Prolog [Nota 9, págs. 1-3]. Prolog es un lenguaje interpretado que internamente ejecuta la resolución: recibe las cláusulas y busca la contradicción para decidir si la meta se sigue [09:00-09:16]. Los predicados sirven para representar conocimiento (relaciones entre personas, cosas, etc.) y se trabaja con ellos mediante la resolución [09:25-09:32].

Unificación y sustitución, el corte y las listas [Nota 9, págs. 4-5]

En Prolog se trabaja con unificación y sustitución (igualar términos, por ejemplo al pasar argumentos) y con el corte (!), que controla el backtracking [Nota 9, pág. 4]. También se manejan listas: una lista es una secuencia de términos o listas separados por comas y delimitados por corchetes; el orden importa. Notaciones: [X | Xs] (primer elemento X y resto Xs), [X, Y | Xs], [] (lista vacía), [X] (un solo elemento) [Nota 9, pág. 5]. [parte no entendida — el detalle de los programas de ejemplo mencionados en clase].

Aplicaciones de Prolog [Nota 9, págs. 6-7]

Aplicaciones típicas de Prolog en inteligencia artificial: dibujar una figura geométrica de un solo trazo sin levantar el lápiz (problema clásico), representación de conocimiento, deducción lógica (probar la veracidad de un argumento), el problema de la Zebra, y la derivada de funciones (manejo de expresiones simbólicas en Prolog) [Nota 9, págs. 6-7]. [parte no entendida — el detalle de la motivación sobre lenguajes declarativos frente a imperativos].

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

6 Glosario de términos

• Resolución: regla de inferencia para la demostración automática en lógica de primer orden (Robinson, 1965).
• Modus ponens: regla de inferencia: si Q implica P y Q, entonces P.
• Explosión combinatoria: crecimiento muy grande de las combinaciones a probar en una demostración automática.
• Cláusula de Horn: cláusula con a lo sumo una literal no negada; la base de Prolog.
• Cláusula vacía: la contradicción que indica que una meta se sigue de las premisas.
• Programación Lógica: paradigma que usa la lógica de primer orden como base de programación.
• Prolog: lenguaje interpretado de programación lógica que ejecuta internamente la resolución.
• Unificación: proceso de igualar términos (por ejemplo, al sustituir variables).
• Sustitución: reemplazo de variables por términos al unificar.
• Corte (`!`): operador de Prolog que controla el backtracking.
• Lista: secuencia de términos o listas delimitada por corchetes; [X|Xs], [X,Y|Xs], [], [X].
• Backtracking: mecanismo de Prolog que vuelve atrás para probar alternativas.
• Predicado: relación entre términos que tiene un valor de verdad (p. ej. da(regalo, juan, maria)).
• Representación de conocimiento: uso de hechos y reglas para modelar información en Prolog.

7 Mapa mental textual

• Programación en Prolog: resolución, cláusulas y aplicaciones · Clase 9
  • Resolución
    • Regla de Robinson: P ∨ Q y ¬Q ⇒ P
    • Demostración automática: negar la meta → aplicar resolución → cláusula vacía
    • Inconveniente: explosión combinatoria → restricción a cláusulas de Horn
  • Prolog
    • Lenguaje interpretado de programación lógica
    • Entornos: SWI-Prolog, Visual Prolog, GNU Prolog
    • Unificación y sustitución · el corte ! · backtracking
    • Listas: [X|Xs], [X,Y|Xs], [], [X]
  • Aplicaciones de Prolog
    • Figura de un solo trazo
    • Representación de conocimiento
    • Deducción lógica (probar argumentos)
    • Problema de la Zebra
    • Derivada de funciones (expresiones simbólicas)